/**
 * @author VernHe
 * @date 2021年05月11日 14:16
 */
public class Solution_042 {
    public static void main(String[] args) {
        System.out.println(new Solution_042().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

    public int trap(int[] height) {
        int res = 0;
        int len = height.length;
        if (len < 3) {
            return res;
        }
        // left_max_arr表示当前位置左侧最高的柱子高度
        int[] left_max_arr = new int[len];
        // right_max_arr表示当前位置右侧最高柱子的高度
        int[] right_max_arr = new int[len];
        left_max_arr[0] = height[0];
        right_max_arr[len - 1] = height[len - 1];

        for (int i : height) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 初始化数组
        for (int i = 1; i < len; i++) {
            left_max_arr[i] = Math.max(left_max_arr[i-1],height[i]);
        }
        for (int i : left_max_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i = len - 2; i >= 0; i--) {
            right_max_arr[i] = Math.max(right_max_arr[i + 1], height[i]);
        }
        for (int i : right_max_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i = 0; i < len; i++) {
            res += (Math.min(left_max_arr[i],right_max_arr[i]) - height[i]);
        }
        return res;
    }
}
